COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	set[f84,jmc]		Notes on set equations
C00005 ENDMK
C⊗;
set[f84,jmc]		Notes on set equations

	We begin with equation

(1)	S = A + SxS

taken from (McCarthy 1963).

Solved as a quadratic for  S  and expanded by the binomial theorem,
this gives the number of kinds of S-expressions with each number of
atoms.  The power series in  A  that we obtain is the same as the
power series for the generating function of the Catalan numbers,
which are defined as the number of ways a product of  n  terms
can be parenthesized.

[Schroeppel (1984 Nov) says that  S = A + S↑k  also leads to a
simple expression for the number of kinds with each number of atoms.
He said he got it from Gosper and that it involves factorials.]

	We have the following intuitions.

	1. There is more to be obtained from (1) than just the generating
function.  We aren't merely interested in counting S-expressions; we
hope to get facts about mappings of S-expressions from (1).

	2. Other sets have similar set equations and they are also
useful.

	Don Knuth referred me to (Polya 1956) when asked whether there
was previous work in combinatorics where the interest was in the set
equations.  The Polya paper contains three instructive examples,
but his interest is after all in deriving equations for the generating
function and not in the set mappings themselves.  It is certainly
worthwhile trying to see whether there is more in Polya's examples
than Polya obtained.

	Is Polya sufficiently compos mentis to make it worthwhile asking
him about it?

	The calculus of (McCarthy 1963) contains only examples of
polynomial set equations.  Exponential set equations are also important,
and Polya's third example of rooted trees shows this.

Polya, George (1956): ``On Picture-writing'', {\it American Mathematical
Monthly}, {\bf 53}, pp. 689-697.

Rota, Gian-Carlo (papers lent by the Chudnovskys)